# -*- coding=utf-8 -*-

# 给定一个未排序的整数数组，找出其中没有出现的最小的正整数

# 示例 1:
# 输入: [1,2,0]
# 输出: 3

# 示例 2:
# 输入: [3,4,-1,1]
# 输出: 2

# 示例 3:
# 输入: [7,8,9,11,12]
# 输出: 1

# 说明:
# 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间

# 一周时间没有想到答案，查看讨论区找到的解题思路
# 思路如下：
# 第一遍遍历数组，把数值[1,length]之间的数字放在对应的下标上
# 第二遍遍历数组，如果对应下标上放置的不是对应的数字，则是即是未出现的数字
#              如果所有下标都是对应的数字，则未出现的数字是length + 1

# 思考问题的时候，没注意到一个隐含的条件，也就是我们不必考虑value > length的数字
# 只需要考虑[1, length]之间的这些数字即可

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        index = 0;
        length = len(nums);
        while index < length:
            if(nums[index] == index + 1):
                index += 1;
                continue;

            value = nums[index];

            while (value > 0 and value <= length and nums[value - 1] != value):
                temp = nums[value - 1];
                nums[value - 1] = value;
                value = temp;
            index += 1;

        for index in xrange(0, length):
            if(nums[index] == index + 1):
                continue;
            return index + 1;
        return length + 1;

t = Solution();
print t.firstMissingPositive([3,4,-1,1])